package com.zk.algo;

import java.util.*;

/**
 * 电话号码分身
 *
 * (1) 没做出来.陷入到 [随机字符串 --> 数字 --> 原来数值] 如何找到这个数字
 *
 * (2) 看别人答案:
 * 链接：https://www.nowcoder.com/questionTerminal/493d71a992f44554a500ed818056e1a6
 来源：牛客网

 要先依次解码具有独一无二字符的数字，具有这样特点的数字有五个分别是FOUR(U),SIX(X),
 TWO(W),EIGHT(G),ZERO(Z),可以根据独特字符的个数直接判断有多少个相应的数字，例如有
 3个U那么就一定有3个FOUR...,解码完成这五个数字之后另外的数字也会由于这些数字的移除
 而具有了独一无二的字符，这样的数字有FIVE(F)，THREE(T),FIVE找到之后，只有SEVEN含
 有V,所以又可以依据V字符的个数解码SEVEN的个数，最后剩下的ONE和NINE也具有了自己的
 标志性字符分别是ONE(O),NINE(I)，需要注意的是原始数字和最终出现的数字还有一个转换
 的过程（加8取个位数），所以还要相应转换回去。
 *
 * (3) list 上错误地调用了 append 方法
 * (4) 先读取数字,然后读取字符串,应该用 nextLine() 读取一下那个换行符
 * (5) beforeNum 可能为 2 位
 * (6) 删除的是这个单词的所有字符,而非单个字符
 * (7) 在源代码中错误地穿插了其他 DEBUG print 字符信息
 * (8) stringBuilder.indexOf("字符串而非单个字符");
 *
 */
public class DianHuaHaoMaFenShen {

    public static void main(String...args) {

        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();
        scanner.nextLine();

        while (T-- > 0) {
            String str = scanner.nextLine();
            String origin = toSmallestNumStr(toOriginIntegerList(toIntegerList(str)));
            System.out.println(origin);
        }
    }

    static String toSmallestNumStr(List<Integer> integerList) {
        Collections.sort(integerList);

        StringBuilder sb = new StringBuilder(integerList.size());
        for (Integer num:integerList) {
            sb.append(num.intValue());
        }

        return sb.toString();
    }

    static List<Integer> toOriginIntegerList(List<Integer> integerList) {
        for (int i=0; i<integerList.size(); i++) {
            int afterNum = integerList.get(i);
            if (afterNum != 9) {
                afterNum = afterNum + 10;
            }

            int beforeNum = afterNum - 8;
            // beforeNum 可能为 10, 2位
            if (beforeNum >= 10) {
                beforeNum -= 10;
            }

            integerList.set(i, beforeNum);
        }

        return integerList;
    }

    static List<Integer> toIntegerList(String str) {
        StringBuilder sb = new StringBuilder(str);
        List<Integer> integerList = new ArrayList<>();

        while (sb.indexOf("Z") != -1) {
            // 一开始删除的是单个字符,而非所有字符
            sb.deleteCharAt(sb.indexOf("Z"));
            sb.deleteCharAt(sb.indexOf("E"));
            sb.deleteCharAt(sb.indexOf("R"));
            sb.deleteCharAt(sb.indexOf("O"));
            integerList.add(0);
        }

        while (sb.indexOf("W") != -1) {
            sb.deleteCharAt(sb.indexOf("T"));
            sb.deleteCharAt(sb.indexOf("W"));
            sb.deleteCharAt(sb.indexOf("O"));
            integerList.add(2);
        }

        while (sb.indexOf("U") != -1) {
            sb.deleteCharAt(sb.indexOf("F"));
            sb.deleteCharAt(sb.indexOf("O"));
            sb.deleteCharAt(sb.indexOf("U"));
            sb.deleteCharAt(sb.indexOf("R"));
            integerList.add(4);
        }

        while (sb.indexOf("X") != -1) {
            sb.deleteCharAt(sb.indexOf("S"));
            sb.deleteCharAt(sb.indexOf("I"));
            sb.deleteCharAt(sb.indexOf("X"));
            integerList.add(6);
        }

        while (sb.indexOf("G") != -1) {
            sb.deleteCharAt(sb.indexOf("E"));
            sb.deleteCharAt(sb.indexOf("I"));
            sb.deleteCharAt(sb.indexOf("G"));
            sb.deleteCharAt(sb.indexOf("H"));
            sb.deleteCharAt(sb.indexOf("T"));
            integerList.add(8);
        }

        while (sb.indexOf("F") != -1) {
            sb.deleteCharAt(sb.indexOf("F"));
            sb.deleteCharAt(sb.indexOf("I"));
            sb.deleteCharAt(sb.indexOf("V"));
            sb.deleteCharAt(sb.indexOf("E"));
            integerList.add(5);
        }

        while (sb.indexOf("T") != -1) {
            sb.deleteCharAt(sb.indexOf("T"));
            sb.deleteCharAt(sb.indexOf("H"));
            sb.deleteCharAt(sb.indexOf("R"));
            sb.deleteCharAt(sb.indexOf("E"));
            sb.deleteCharAt(sb.indexOf("E"));
            integerList.add(3);
        }

        while (sb.indexOf("V") != -1) {
            sb.deleteCharAt(sb.indexOf("S"));
            sb.deleteCharAt(sb.indexOf("E"));
            sb.deleteCharAt(sb.indexOf("V"));
            sb.deleteCharAt(sb.indexOf("E"));
            sb.deleteCharAt(sb.indexOf("N"));
            integerList.add(7);
        }

        while (sb.indexOf("O") != -1) {
            sb.deleteCharAt(sb.indexOf("O"));
            sb.deleteCharAt(sb.indexOf("N"));
            sb.deleteCharAt(sb.indexOf("E"));
            integerList.add(1);
        }

        while (sb.indexOf("I") != -1) {
            sb.deleteCharAt(sb.indexOf("N"));
            sb.deleteCharAt(sb.indexOf("I"));
            sb.deleteCharAt(sb.indexOf("N"));
            sb.deleteCharAt(sb.indexOf("E"));
            integerList.add(9);
        }

        return integerList;
    }

}
